//
//  AddStrings.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/8/3.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  415. 字符串相加  43.字符串相乘

import UIKit

/*
 415. 字符串相加

 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

 注意：

 num1 和num2 的长度都小于 5100.
 num1 和num2 都只包含数字 0-9.
 num1 和num2 都不包含任何前导零。
 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
 */

class AddStrings: NSObject {

    var ASCIIMemeri:[String:Int] = [:]
    
    func addStrings(_ num1: String, _ num2: String) -> String {

        var result:[String] = []
        //以下方法可以直接把字符串转成数组 大大提升效率。
        let array1 = Array(num1)
        let array2 = Array(num2)
        
        var l1 = num1.count - 1
        var l2 = num2.count - 1
        //记录加法进位
        var carry = 0
        
        while l1 != -1 || l2 != -1 {
            // '0' 的ASCII值为48
            /*
             通过数组下标直接访效率很高 从 788ms 直接提升到 28ms
             str[str.index(str.startIndex, offsetBy: 0)] 这种写法以后都可以用直接转数组然后访问下表代替
             */
            let adder1 = l1 == -1 ? 0 : self.StringToASCIINum(String(array1[l1])) - 48
            let adder2 = l2 == -1 ? 0 : self.StringToASCIINum(String(array2[l2])) - 48
            
            
            let sum = adder1 + adder2 + carry
            
            carry = sum/10
            let singRes = sum%10
            let str = self.ASCIINumToString(48+singRes)
            
            result.append(String(str))
            
            if l1 != -1{
                l1 -= 1
            }
            if l2 != -1{
                l2 -= 1
            }
            
            if l1 == -1 && l2 == -1 && carry != 0{
                result.append(String(carry))
            }
        }
        
        return result.reversed().joined(separator: "")
    }
    
    //String to ascii Num
    func StringToASCIINum(_ string: String) -> Int{
        
        guard ASCIIMemeri[string] == nil else {
            return ASCIIMemeri[string]!
        }
        let str = string
        var number:UInt32 = 0
        for code in str.unicodeScalars {
            number = code.value;
        }
        ASCIIMemeri[string] = Int(number)
        return Int(number)
    }
    
    //ascii Num to String
    func ASCIINumToString(_ asciiNum: Int) -> String{
        let num = asciiNum
        let ch:Character = Character(UnicodeScalar(num)!)
        return String(ch)
    }
    
    
    /*
     43. 字符串相乘
     给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

     示例 1:

     输入: num1 = "2", num2 = "3"
     输出: "6"
     示例 2:

     输入: num1 = "123", num2 = "456"
     输出: "56088"
     */
    
    
    /*
     模拟乘法竖式
            1 2 3 4
          x   5 6 7
     -------------------
            8 6 3 8
          7 4 0 4
        6 1 7 0
     -------------------
        6 9 9 6 7 8
     
     =====>>>>
     
     1 2 3 4                      1 2 3 4                   1 2 3 4
     x     7          +         x     6          +         x  5
    ----------                  ----------                 ---------
     8 6 3 8                    7 4 0 4 0                6 1 7 0 0 0
     
     
     */
    func multiply(_ num1: String, _ num2: String) -> String {
        if num1 == "0" || num2 == "0"{
            return "0"
        }
        
        var sumString = "0"
        
        let array1 = Array(num1)
        let array2 = Array(num2)
        
        let l1 = array1.count
        let l2 = array2.count
        
        //模拟乘法竖式    注意补0
        for i in (0 ... l2-1).reversed(){
            
            //本轮乘积结果
            var resultIntArr:[String] = []
            
            //补0
            for _ in 0 ..< l2-1-i{
                resultIntArr.append("0")
            }
            
            //记录进位
            var carry = 0
            
            for j in (0 ... l1-1).reversed(){
                
                let mul1 = Int(String(array1[j]))!
                let mul2 = Int(String(array2[i]))!
                
                let sum = mul1 * mul2 + carry
                
                carry = sum/10
                
                let res = String(sum%10)
                
                resultIntArr.append(res)
                
            }
            //乘数已经加完 但是还有进位
            if carry != 0 {
                resultIntArr.append(String(carry))
            }
            
            let curentString = resultIntArr.reversed().joined(separator: "")
            sumString = self.addStrings(sumString, curentString)
        }
        return sumString
    }
}
